package org.marverse.util

import scala.collection.Set

/** <p>
 *    A typed map is a collection that maps each typed key to one or zero values,
 *    where the values are typed checked against their keys.
 *  </p>
 *  <p>
 *    This trait provides a limited interface, only allowing reading of elements.
 *    There is one extensions of this trait, {@link MutableTypedMap}, which provides 
 *    functionality for adding new key/value mappings to a map. The trait is
 *    for maps that are modified destructively.
 *  </p>
 *
 *  @author  Matthias Zenger
 *  @author  Martin Odersky
 *  @author  Stefan Bohne
 */
trait TypedMap[K[T] <: TypedKey[T], +V] extends Collection[(K[_], V)] {

  /** Compute the number of key-to-value mappings.
   *
   *  @return the number of mappings
   */
  def size: Int

  /** Check if this map maps <code>key</code> to a value and return the
   *  value if it exists.
   *
   *  @param  key the key of the mapping of interest
   *  @return     the value of the mapping, if it exists
   */
  def get[V1](key: K[V1]): Option[V1]
    
  /** Check if this map maps <code>key</code> to a value.
    *  Return that value if it exists, otherwise return <code>default</code>.
    */
  def getOrElse[V1, R >: V1](key: K[V1], default: => R): R =
    get(key) match {
      case Some(v) => v
      case None => default 
    }

  /** Is this an empty map?
   *
   *  @return <code>true</code> iff the map is empty.
   */
  override def isEmpty: Boolean = size == 0

  /** Retrieve the value which is associated with the given key. This
   *  method throws an exception if there is no mapping from the given
   *  key to a value.
   *
   *  @param  key the key
   *  @return     the value associated with the given key.
   */
  def apply[V1](key: K[V1]): V1 = get(key) match {
    case None => default(key)
    case Some(value) => value
  }

  /** Is the given key mapped to a value by this map?
   *
   *  @param key the key
   *  @return    <code>true</code> iff there is a mapping for key in this map
   */
  def contains(key: K[_]): Boolean = get(key) match {
    case None => false
    case Some(_) => true
  }

  /** Does this map contain a mapping from the given key to a value?
   *
   *  @param key the key
   *  @return    <code>true</code> iff there is a mapping for key in this map
   */
  def isDefinedAt[V1](key: K[V1]) = contains(key)

  /** Creates an iterator for all keys.
   *
   *  @return an iterator over all keys.
   */
  def keys: Iterator[K[_]] = new Iterator[K[_]] {
    val iter = TypedMap.this.elements
    def hasNext = iter.hasNext
    def next = iter.next._1
  }

  /** @return the keys of this map as a set. 
   */
  def keySet: Set[K[_]] = new Set[K[_]] {
    def size = TypedMap.this.size
    def contains(key : K[_]) = TypedMap.this.contains(key)
    def elements = TypedMap.this.elements.map(_._1)
  }

  /** Creates an iterator for a contained values.
   *
   *  @return an iterator over all values.
   */
  def values: Iterator[V] = new Iterator[V] {
    val iter = TypedMap.this.elements
    def hasNext = iter.hasNext
    def next = iter.next._2
  }

  /** Compares two maps structurally; i.e. checks if all mappings
   *  contained in this map are also contained in the other map,
   *  and vice versa.
   *
   *  @param that the other map
   *  @return     <code>true</code> iff both maps contain exactly the
   *              same mappings.
   */
  override def equals(that: Any): Boolean = that match {
    case other: TypedMap[_, _] =>
      this.size == other.size && this.elements.forall {
        case (key, value) => other.get(key) match {
          case None => false
          case Some(otherval) => value == otherval
        }
      }
    case _ => false
  }

  /** A hash method compatible with <code>equals</code> 
   */
  override def hashCode() =
    (0 /: elements) ((hash, kv) => hash + kv.hashCode)


  /** Creates a string representation for this map.
   *
   *  @return    a string showing all mappings
   */
  override def toString() =
    elements.toList.map(kv => kv._1 + " -> " + kv._2).mkString(stringPrefix + "(", ", ", ")")
    
  /** The default value for the map, returned when a key is not found
   *  The method implemented here yields an error,
   *  but it might be overridden in subclasses.
   *
   *  @param key the given key value
   *  @throws Predef.NoSuchElementException
   */
  def default[V1](key: K[V1]): V1 =
    throw new NoSuchElementException("key not found: " + key)
    
  /** Defines the prefix of this object's <code>toString</code> representation.
   */
  override protected def stringPrefix: String = "TypedMap"
}
